The previous post covered several levels of tests for assessing the correctness of scientific computation. Now let us look at reasons why the results might not match what is expected.
- Programming errors
- Mistakes in derivation and transcription of equations
- Violations of assumptions or conventions
- Errors from floating point
- Errors and undesirable behavior from the algorithm (often problem-dependent)
- Algorithms that have been well-studied by numerical analysts
- Those that have not
- Algorithms that have been well-studied by numerical analysts
Programming errors
The usual sorts of problems in programs (array indices, memory problems, etc). This category of problems can be tested with unit tests and can make use of tools and practices from mainstream software engineering.
Mistakes in derivation and transcription of equations
This is similar to the implementation not matching the specification in traditional software engineering. With scientific computation, though, the "specification" could be more precise in principle (equations and algorithms), and computer algebra systems could aid with performing and verifying steps in the derivation.
Violations of assumptions or conventions
Usually happens during derivation of the equations. A stronger connection between the derivation and the final code might help this.
Errors and instabilities from floating point
Accumulated round-off, loss of precision from subtracting nearly equal numbers, and other problems. For more subtleties than you every wanted to know about, visit W. Kahan's site.
One of the most annoying parts about floating point is lack of good model for understanding (and analyzing) floating point errors. I will return to this issue in a future post.
Errors and instabilities from the algorithm.
This category might be better divided into two subcategories - algorithms that have been well-studied by numerical analysts (like matrix operations, certain ODE's and PDE's, optimization), and those that have not. Many algorithms have been well-studied and have nice packages available to use as black-boxes. However, most scientific programs are a composition of well-known algorithms along with some problem-dependent features as well.
Often times the behavior of the algorithm depends on the details of the physical system (ie, is it a metal or insulator)?
This category also includes science-based and numerical approximations.
Now, how do we go from test case failure to deciding which of these categories the problem falls into (and then, of course, to locating the precise problem)?
- Unit testing will help with the first category. But not so much with the rest. Unit testing is helpful when you want to make sure things haven't changed. The hard part is getting it right the first time.
- The different levels of tests in the previous post should give some insight into which category the problem might occur.
First I want to look at various models of floating point error and see if we can gain some understanding of the intrinsic uncertainty in a calculation. This seems to be a necessary prerequisite for answering the question of 'how close is close enough?', in order to decide whether a test has actually failed or not.